Листинг 12.4. Алгоритм поиска в графах AND-OR, сформированных в условиях недетерминированных вариантов среды. Предполагается, что функция Successors возвращает список действий, каждое из которых связано с множеством возможных результатов. Задача состоит в том, чтобы найти условный план, который достигает целевого состояния во всех обстоятельствах

Планы, возвращаемые алгоритмом And-Or-Graph-Search, содержат условные шаги, в которых проверяется описание всего состояния для выбора следующей ветви. Но во многих случаях можно справиться с этой работой с помощью менее исчерпывающих проверок. Например, план решения на рис. 12.6 может быть записан просто как [Left, if CleanL then [ ] else Suck]. Это связано с тем, что достаточно провести единственную проверку, CleanL, для разделения состояния в узле AND на два одноэлементных множества, чтобы после проверки агент мог точно определить, в каком состоянии он находится. В действительности проведение ряда проверок по принципу "if—then—else" отдельных переменных всегда позволяет разделить множество состояний на одноэлементные множества, при условии, что среда является полностью наблюдаемой. Поэтому можно без потери общности ограничиться проведением проверок отдельных переменных.